package com.atcumt.lcSolution;

import java.util.*;

/**
 * 栈
 */
public class LC3 {

    // 遍历字符串，准备一个栈，存放字符串下标，首先放入初始参照物-1，遇到'('入栈，遇到')'出栈;
    // 判断栈长度，如果不为空，更新最大合法字符串长度，否则将当前下标放入栈中
    public int longestValidParentheses(String s) {
        int maxLen = 0;
        Deque<Integer> stack = new LinkedList<>();
        stack.push(-1);

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (!stack.isEmpty()) {
                    // 每次出栈计算当前有效连续长度
                    maxLen = Math.max(maxLen, i - stack.peek());
                } else {
                    stack.push(i);
                }
            }
        }
        return maxLen;
    }

    /**
     * 前k个高频元素
     *
     * 输入: nums = [1,1,1,2,2,3], k = 2
     * 输出: [1,2]
     *
     * 1.使用集合，统计每个元素出现的次数，元素为键，元素出现的次数为值
     * 2.遍历 map，用最小堆保存频率最大的k个元素
     * 3.取出最小堆中的元素
     *
     */
    public int[] topKFrequent(int[] nums, int k) {

        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
        // 遍历 map的 k-v，根据map的value值正序排，相当于用最小堆保存频率最大的k个元素
        PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((o1, o2) -> o1.getValue() - o2.getValue());

        for (Map.Entry<Integer, Integer> entry : entries){
            queue.offer(entry);
            if (queue.size() > k) {
                queue.poll();
            }
        }

        int[] res = new int[k];
        int index = 0;
        while (!queue.isEmpty()) {
            res[index++] = queue.poll().getKey();
        }
        return res;
    }
}
